package problems.daily.y2021m6;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author habitplus
 * @since 2021-06-27 09:10
 */
public class T20210627N1 {
    /**
     * 909. 蛇梯棋
     * 题目链接：https://leetcode-cn.com/problems/snakes-and-ladders/
     */
    public int snakesAndLadders(int[][] board) {
        // bfs：为了加快判断该位置是否已经访问过，可以使用 boolean 数组
        int n = board.length;
        // int[0]: 表示位置编号（1 ~ n*n）；int[1]: 记录步数
        Queue<int[]> que = new LinkedList<>();
        // 标记到过的位置
        boolean[] visited = new boolean[n * n + 1];

        // 设置初始状态
        que.offer(new int[]{1, 0});
        visited[1] = true;

        while (!que.isEmpty()) {
            for (int i = que.size(); i > 0; i--) {
                int[] curStatus = que.poll();
                // 枚举六个位置
                for (int k = 1; k < 7; k++) {
                    int nxtPos = curStatus[0] + k;
                    if (nxtPos > n * n) {
                            break;
                    }

                    int[] d = getPosition(nxtPos, n);
                    // 是梯子或蛇就得继续走
                    if (board[d[0]][d[1]] != -1) {
                        nxtPos = board[d[0]][d[1]];
                    }

                    if (nxtPos == n * n) {
                        return curStatus[1] + 1;
                    }

                    if (!visited[nxtPos]) {
                        que.offer(new int[]{nxtPos, curStatus[1] + 1});
                        visited[nxtPos] = true;
                    }

                }
            }
        }
        return -1;
    }

    private int[] getPosition(int pos, int n) {
        int i = (pos - 1) / n, j = (pos - 1) % n;
        j = i % 2 == 0 ? j : n - j - 1;
        return new int[]{n - 1 - i, j};
    }

    public static void main(String[] args) {
        int[][] b = {
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, 35, -1, -1, 13, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, 15, -1, -1, -1, -1}
        };
        System.out.println(new T20210627N1().snakesAndLadders(b));
    }

}
